﻿using System;
using System.Collections.Generic;
using System.Numerics;

namespace ProjectEulerIssues
{
	public static class Misc
	{
		public static HashSet<long> esieve(int limit)
		{
			HashSet<long> primes = new HashSet<long>();
			primes.Add(2);
			for (long i = 3; i < limit; i += 2)
			{
				primes.Add(i);
			}
			long j = 3;
			while (j < limit)
			{
				while (!primes.Contains(j) && j < limit)
				{
					j++;
				}
				for (long j2 = j + j; j2 < limit; j2 += j)
				{
					if (primes.Contains(j2))
					{
						primes.Remove(j2);
					}
				}
				j++;
			}
			return primes;
		}

		public static HashSet<long> getPrimes(int limit)
		{
			HashSet<long> primes = new HashSet<long>() { 2, 3, 5, 7, 11, 13, 17 };
			var found = false;
			for (long i = 19; i <= limit; i += 2)
			{
				found = false;
				foreach (var pr in primes)
				{
					if (pr > Math.Sqrt(i))
					{
						break;
					}
					if (i % pr == 0)
					{
						found = true;
						break;
					}
				}
				if (!found)
				{
					primes.Add(i);
				}
			}
			return primes;
		}

		public static Dictionary<long, long> dissolve(long num, HashSet<long> primes)
		{
			var nm = new Dictionary<long, long>();
			if (primes.Contains(num))
			{
				nm.Add(num, 1);
				return nm;
			}
			foreach (var pr in primes)
			{
				while (num % pr == 0)
				{
					if (!nm.ContainsKey(pr))
						nm.Add(pr, 0);
					nm[pr]++;
					num /= pr;
				}
				if (primes.Contains(num))
				{
					break;
				}
				if (pr > Math.Sqrt(num))
				{
					break;
				}
			}
			if (num > 1)
			{
				if (!nm.ContainsKey(num))
					nm.Add(num, 0);
				nm[num]++;
			}
			return nm;
		}

		public static bool isPrime(BigInteger num, HashSet<long> primes)
		{
			if (primes.Contains((long)num))
			{
				return true;
			}
			var numSqrt = num.Sqrt();
			foreach (var pr in primes)
			{
				if (pr > numSqrt)
				{
					return true;
				}
				if (BigInteger.Remainder(num, pr) == 0)
				{
					return false;
				}
			}
			return true;
		}

		public static bool isPrime(long num, HashSet<long> primes)
		{
			if (primes.Contains(num))
			{
				return true;
			}
			var numSqrt = Math.Sqrt(num);
			foreach (var pr in primes)
			{
				if (pr > numSqrt)
				{
					return true;
				}
				if (num % pr == 0)
				{
					return false;
				}
			}
			return true;
		}

		public static long gcd(long a, long b)
		{
			long y = 0;
			long x = 0;

			if (a > b)
			{
				x = a;
				y = b;
			}
			else
			{
				x = b;
				y = a;
			}

			while (x % y != 0)
			{
				long temp = x;
				x = y;
				y = temp % x;
			}
			return y;
		}

		public static HashSet<BigInteger> divisors(BigInteger num, HashSet<long> primes)
		{
			var divs = new HashSet<BigInteger>() { 1 };
			foreach (BigInteger pr in primes)
			{
				if (pr > num)
				{
					break;
				}
				if (num % pr == 0)
				{
					BigInteger pr1 = pr;
					while (pr1 <= num)
					{
						if (num % pr1 == 0)
						{
							divs.Add(pr1);
							BigInteger aPr = (num / pr1) * num;
							if (aPr <= 2 * num)
							{
								divs.Add(aPr);
							}
							pr1 *= pr;
						}
						else
						{
							break;
						}
					}
				}
			}
			return divs;
		}
	}
}
